👉 diff 算法

diff 算法是通过同层之间的树节点进行比较，时间复杂度只有 O(n), 算是一个较高效的算法。

why diff

• 数据变化，vue 如何更新节点

  会先根据真实的 DOM 节点结构生成 virtual DOM，当 virtual DOM 某个节点的数据改变后，会生成一个新虚拟节点 vnode。

  触发 set 方法后，消息发布器 Dep 调用 Dep.notify 通知所有订阅者 watcher，订阅者的回调函数 vm.update(vm.render())，vm.render()就是生成的新 vnode， vm.update(）就会带着新 vnode，和旧虚拟节点 oldVnode 作对比，给真实的 DOM 打补丁，最后更新相应的视图。

• virtual DOM 和真实 DOM 区别

  使用 document.CreateElement 和 document.CreateTextNode 创建的就是真实节点。

  virtual DOM 是将真实的 DOM 的数据抽取出来，以对象的形式模拟树形结构：

  <div id="test" class="div1">
      <p class="p1"></p>
      <p class="p2"></p>
  </div>
  

  对应以下虚拟 DOM 对象

  const vnode = {
      el: div, //对真实的节点的引用，本例中对应document.querySelector('#test.div1')
      tag: "div", //节点的标签
      sel: "div#test.div1", //节点的选择器
      data: null, // 一个存储节点属性的对象，对应节点的el[prop]属性，例如onclick , style
      text: null, //如果是文本节点，对应文本节点的textContent，否则为null
      children: [
          {
              el: p,
              tag: "p",
              sel: "p.p1",
              data: null,
              text: null,
              children: [],
          },
          {
              el: p,
              tag: "p",
              sel: "p.p2",
              data: null,
              text: null,
              children: [],
          },
      ], //存储子节点的数组，每个子节点也是 vnode 结构
  };
  

  virtual DOM 本质是在 JS 操控 DOM 的过程中进行一个缓存。使用真实 DOM 对更新的数据重绘整个视图层是相当消耗性能，通过虚拟 DOM 和 diff 算法得出一些需要修改的最小单位，并对小单位的位图作出对应的更新，这样子可以减少不必要的 DOM 操作，以此来提高性能。

• diff 比较方式

  diff 通过 patch 函数像打补丁一样修改真实 DOM。比较只会在同层级进行, 不会跨层级比较。

• Vue2.0 diff 过程简述：

1） 通过patch对同级进行比较，然后再往下比较子节点；

首先会通过sameNode判断两个节点的 key、tag、isComment、data 同时定义或不定义以及当标签类型为 input 的时候的 type 相不相同来确定两个节点是不是相同的节点：
如果不是的话就将新节点替换旧节点；
如果是相同节点的话才会进入到 patchVnode 阶段。

2）patchVnode 阶段中，会有几种情况的判断：
a. 判断节点引用是否完全一致，是则直接 return；

b. 然后会对文本节点进行判断，如果是文本节点并且不相等，那么将真实 DOM 对应的文本节点设置为 Vnode 的文本节点；

c. 然后再判断一方有子节点和一方没有子节点的情况：
如果旧的一方没有而新一方有子节点，则添加创建并添加新的子节点；
如果旧的一方有而新一方没有子节点，则把旧子节点删除；

d. 最后是判断双方都存在子节点的情况，是则执行 updateChildren 操作。

3）通过 updateChildren 来更新子节点：

在这个阶段核心是采用双端比较的算法，同时从新旧节点的两端进行比较。
在这个过程中，会用到模版编译时的静态标记配合 key 来跳过对比静态节点（没有涉及 data 数据{{}}）。

patch

diff 的过程就是调用 patch 函数，就像打补丁一样修改真实 dom。

patch 函数有两个参数，vnode 和 oldVnode，也就是新旧两个虚拟节点。

function patch(oldVnode, vnode) {
    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode);
    } else {
        // 当前oldVnode对应的真实元素节点
        const oEl = oldVnode.el;

        // 父元素
        let parentEle = api.parentNode(oEl);

        // 根据Vnode生成新元素
        createEle(vnode);

        if (parentEle !== null) {
            // 将新元素添加进父元素
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl));

            // 移除以前的旧元素节点
            api.removeChild(parentEle, oldVnode.el);
            oldVnode = null;
        }
    }

    // patch最后会返回vnode，vnode和进入patch之前的不同在哪
    return vnode;
}

sameNode

/*
  判断两个VNode节点是否是同一个节点，需要满足以下条件：
  key相同
  tag相同（当前节点的标签名）
  isComment相同（是否为注释节点）
  是否data都有定义（当前节点对应的对象，包含了具体的一些数据信息，是一个VNodeData类型，可以参考VNodeData类型中的数据信息）
  当标签是<input>时，type是否相同
*/
function sameVnode(a, b) {
    return (
        a.key === b.key &&
        a.tag === b.tag &&
        a.isComment == b.isComment &&
        isDef(a.data) == isDef(b.data) &&
        sameInputType(a, b)
    );
}

/*
  判断当标签是<input>的时候，type是否相同
  某些浏览器不支持动态修改<input>类型，所以他们被视为不同类型
*/
function sameInputType(a, b) {
    if (a.tag !== "input") return true;

    let i;
    const typeA = isDef((i = a.data)) && isDef((i = i.attrs)) && i.type;
    const typeB = isDef((i = b.data)) && isDef((i = i.attrs)) && i.type;
    return typeA === typeB;
}

patchNode

当 oldVnode 和 Vnode 值得比较后，会对两个节点执行 patchNode：

function patchVnode(oldVnode, vnode) {
    // 引用一致则直接返回
    if (oldVnode === vnode) return;

    // 指向对应的真实DOM
    // vnode表示新节点，此时是没有elm属性的。而在经过createElm方法后，vnode.children中的子节点都有了elm属性，此时只有vnode没有elm属性，而能进到 patchVnode 方法来的新旧节点，一定经过了sameVnode方法的判断，说明他们节点本身几乎一样，所以新节点可以用旧节点的elm
    const el = (vnode.el = oldVnode.el);

    let i;
    let oldCh = oldVnode.children;
    let ch = vnode.children;

    // 如果他们都有文本节点并且不相等，那么将el的文本节点设置为vnode的文本节点
    if (
        oldVnode.text !== null &&
        vnode.text !== null &&
        oldVnode.text !== vnode.text
    ) {
        // node.textContent = vnode.text
        api.setTextContent(el, vnode.text);
    } else {
        updateEle(el, vnode, oldVnode);

        // 如果oldVnode和vnode都有子节点，则执行updateChildren，对子节点进行比较（diff核心）
        if (oldCh && ch && oldCh !== ch) {
            updateChildren(el, oldCh, ch);
        }

        // 如果oldVnode没有子节点，而vnode有，则将vode的子节点真实化并新增至el
        else if (ch) {
            createEle(vnode);
        }

        // 如果oldVnode有子节点，而vnode没有，则删除el的子节点
        else if (oldCh) {
            api.removeChildren(el);
        }
    }
}

updateChildren

function updateChildren(parentElm, oldCh, newCh) {
    // 提取 oldVNode 子节点的头尾Idx以及节点内容，作为移动指针
    let oldStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];

    // 提取 newVNode 子节点的头尾Idx以及节点内容，作为移动指针
    let newStartIdx = 0;
    let newEndIdx = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];

    // 存储所有旧子节点的Key -> index的哈希表
    let oldKeyToIdx;

    // 新节点匹配旧子节点中的index
    let idxInOld;

    let elmToMove;
    let before;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 边界情况处理
        if (oldStartVnode == null) {
            oldStartVnode = oldCh[++oldStartIdx];
        } else if (oldEndVnode == null) {
            oldEndVnode = oldCh[--oldEnIdx];
        } else if (newStartVnode == null) {
            newStartVnode = newCh[++newStartVnode];
        } else if (newEndVnode == null) {
            newEndVnode = newCh[--newEndIdx];
        }

        // 前四种情况是在有指定key的时候，分别比较oldCh以及newCh的两头节点 2*2=4 种情况。若判定为同一个Vnode则直接patchVnode。

        // 对于 sameVnode(oldStartVnode, newStartVnode) 和 sameVnode(oldEndVnode,newEndVnode) 为 true 的情况，不需要对DOM进行移动
        else if (sameVnode(oldStartVnode, newStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode);

            // 匹配上的两个指针向中间移动
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        } else if (sameVnode(oldEndVnode, newEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode);

            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        } else if (sameVnode(oldStartVnode, newEndVnode)) {
            patchVnode(oldStartVnode, newEndVnode);

            // vnode moved right
            //若oldStartVnode和newEndVnode匹配上了，说明真实DOM的第一个子节点会被移动最后
            api.insertBefore(
                parentElm,
                oldStartVnode.el,
                api.nextSibling(oldEndVnode.el)
            );

            oldStartVnode = oldCh[++oldStartIdx];
            newEndVnode = newCh[--newEndIdx];
        } else if (sameVnode(oldEndVnode, newStartVnode)) {
            patchVnode(oldEndVnode, newStartVnode);

            // vnode moved left
            // 若oldEndVnode和newStartVnode匹配上了，说明真实DOM的最后子节点会被移动最前
            api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el);

            oldEndVnode = oldCh[--oldEndIdx];
            newStartVnode = newCh[++newStartIdx];
        }

        // 如果四种比较都没匹配成功，接下来的比较会分支两种情况：
        // 如果设置了key，就会用key进行比较，根据所有旧子节点的key生成哈希表，key为oldVnode的key，value为对应index序列的哈希表（所有旧子节点的 key 映射到旧节点下标）。
        else {
            // 所有旧子节点的 key 映射到旧节点下标，然后用新vnode的key去找出在旧节点中可以复用的位置。
            // 只有第一次进来undefined的时候会生成，也为后面检测重复的key值做铺垫
            if (oldKeyToIdx === undefined) {
                // 比如oldCh是这样的 [{xx: xx, key: 'key0'}, {xx: xx, key: 'key1'}, {xx: xx, key: 'key2'}]，oldStartIdx = 0，oldEndIdx = 2
                // 生成 {key0: 0, key1: 1, key2: 2}
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
            }

            // 在旧节点中匹配可复用的位置
            idxInOld = oldKeyToIdx[newStartVnode.key];

            // newStartVnode没有key 或 该key没有在老节点中匹配上，则创建一个新的节点插入至oldStartVnode对应位置
            if (!idxInOld) {
                api.insertBefore(
                    parentElm,
                    createEle(newStartVnode).el,
                    oldStartVnode.el
                );
                newStartVnode = newCh[++newStartIdx];
            } else {
                // 匹配上了则获取同key的旧子节点
                elmToMove = oldCh[idxInOld];

                // 相同key，还要判断和匹配节点是否为sameVnode
                if (elmToMove.sel !== newStartVnode.sel) {
                    // 相同key但不是sameVnode的时候，创建新节点并插入至oldStartVnode.el的前边。
                    api.insertBefore(
                        parentElm,
                        createEle(newStartVnode).el,
                        oldStartVnode.el
                    );
                } else {
                    // 相同key且是sameVnode的时候，则将新节点插入，同时往下patchVnode，并把匹配上的旧子节点设置为null
                    pathVnode(elmToMove, newStartVnode);
                    oldCh[idxInOld] = null;
                    api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el);
                }

                newStartVnode = newCh[++newStartIdx];
            }
        }
    }

    // 在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较。
    if (oldStartIdx > oldEndIdx) {
        // oldCh先遍历完，则证明剩下的newCh节点是新增的（newStartIdx和newEndIdx之间的vnode），调用addVnodes将其拆入至before后面
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el;
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx);
    } else if (newStartIdx > newEndIdx) {
        // newCh先遍历完，则在真实DOM中将[oldStartIdx, oldEndIdx]的多余节点删除
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
}